class Solution {
    /*
        思路1：bfs遍历，
        每层的最后一个节点就是右视图
    */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root!=null) q.offer(root);
        while( !q.isEmpty() ){
            int len = q.size();
            for(int i=1;i<=len;i++){
                TreeNode tmp = q.poll();
                if(i==len) 
                    list.add(tmp.val);
                if(tmp.left!=null)
                    q.offer(tmp.left);
                if(tmp.right!=null)
                    q.offer(tmp.right);
            }
        }
        return list;
    }
}


class Solution {
    /*
        思路2：dfs遍历， 我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问，
                        就可以保证每层都是最先访问最右边的节点的。
        空间复杂度： O(N)，因为这不是一棵平衡二叉树，二叉树的深度最少是 logN 
        最坏的情况下会退化成一条链表，深度就是 N，因此递归时使用的栈空间是 O(N) 的。
               1            <---
             /   \
            2     3         <---
             \     \
              5     4       <---
              
            节点：1, 深度：0, 列表大小：0
            节点：3, 深度：1, 列表大小：1
            节点：4, 深度：2, 列表大小：2
            节点：2, 深度：1, 列表大小：3
            节点：5, 深度：2, 列表大小：3      
              
    */
    List<Integer> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root,0);
        return list;
    }
    public void dfs(TreeNode root,int depth){
        if(root == null)
            return;
        // System.out.println("节点："+root.val+", 深度："+depth +", 列表大小："+list.size());
        /*
         如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，
        因此将当前节点加入res中。
        */
        if(depth==list.size()){
            list.add(root.val);
        }
        depth++;
        // 先访问右子树，再访问左子树
        dfs(root.right,depth);
        dfs(root.left,depth);
    }
}